<html lang="en">
<head>
<meta name="viewport" content="width=device-width, initial-scale=1.0">
<meta http-equiv="Content-Type" content="text/html; charset=utf-8">

<link type="text/css" rel="stylesheet" href="../source/css/bootstrap.css" />
<link type="text/css" rel="stylesheet" href="../source/css/bootstrap-responsive.css" />
<link type="text/css" rel="stylesheet" href="../source/css/docs.css" />
<link type="text/css" rel="stylesheet" href="../source/css/monokai.css" />
<link type="text/css" rel="stylesheet" href="../source/css/font-awesome.css">

<script type="text/javascript" src="../source/js/jquery-1.9.1.js"></script>
<script type="text/javascript" src="../source/js/bootstrap.js"></script>
<script type="text/javascript" src="../source/js/highlight.pack.js"></script>
<script type="text/x-mathjax-config"> 
    MathJax.Hub.Config({ 
        tex2jax: {inlineMath: [['$','$'], ['\\(','\\)']]} 
    }); 
</script>
<script type="text/javascript"
    src="http://cdn.mathjax.org/mathjax/latest/MathJax.js?config=TeX-AMS-MML_HTMLorMML">
</script>
<title>String Matching</title>

</head>
<body data-spy="scroll" data-target=".bs-docs-sidebar">
<div class="navbar navbar-fixed-top">
    <div class="navbar-inner">
        <div class="container">
            <!-- .btn-navbar is used as the toggle for collapsed navbar content -->
            <a class="btn btn-navbar" data-toggle="collapse" data-target=".nav-collapse">
                <span class="icon-bar"></span>
                <span class="icon-bar"></span>
                <span class="icon-bar"></span>
            </a>

            <!-- Be sure to leave the brand out there if you want it shown -->
            <a class="brand" href="../index.html">Wahacer's blogs</a>

            <!-- Everything you want hidden at 940px or less, place within here -->
            <div class="nav-collapse collapse">
                <!-- .nav, .navbar-search, .navbar-form, etc -->
                <ul class="nav">
                    <li class="">
                        <a href="../index.html">Index</a>
                    </li>
                    
                    <li class="">
                        <a href="../Solution/index.html">Solution</a>
                    </li>
                    
                    <li class="">
                        <a href="../Algorithm/index.html">Algorithm</a>
                    </li>
                    

                </ul>
            </div>
        </div>
    </div>
</div>

<div class="container-fluid">
    <div class="row-fluid">
        <!--　侧边拦 -->
        <div class="span2 bs-docs-sidebar">
            <br><br><br>
            <div align="center"><img src="../source/picture/photo.jpg" alt="photo" width="250" height="250" /></div>
            <p align="center"><strong>Wahacer</strong></p>

        </div>

        <!-- 主内容　-->
        <div class="span8">
            <br>
            <!--Body content-->
            <h1 id="toc-0">字符串匹配</h1>
<p>概念：</p>
<p><li>文本，相对而言较长的一个，也就是在文本找.</p>
<p><li>模板：相对而言较短的一个，需要匹配的一个.</p>
<p><li>一般的问题就是在文本中找模板.</p>
<blockquote><p>字符串匹配问题：一类典型问题，对于字符串而言，在某一个串中判断另外一个字符串是否存在，这就是字符串匹配问题.</p>
<p>当然还有字符串匹配之外的字符串问题，如：回文串判断等...</p>
</blockquote>
<p>现在怎么处理这个问题?</p>
<h2 id="toc-1">暴力匹配</h2>
<p>我们用暴力匹配的思想，假设文本串S匹配到了i位置，模式串P匹配到j位置，那么就有:</p>
<p><li>如果当前字符匹配成功(S[i]==P[j]) 那么两个指针都往后加一.</p>
<p><li>不成功就回溯，重新找.</p>
<h4 id="toc-2">talk is cheap , show me the code!</h4>
<div class="highlight"><pre><span></span><span class="kt">int</span> <span class="nf">baoni</span><span class="p">(</span><span class="kt">char</span><span class="o">*</span> <span class="n">s</span><span class="p">,</span><span class="kt">char</span><span class="o">*</span> <span class="n">p</span><span class="p">){</span>
    <span class="kt">int</span> <span class="n">slen</span><span class="o">=</span><span class="n">strlen</span><span class="p">(</span><span class="n">s</span><span class="p">);</span>
    <span class="kt">int</span> <span class="n">plen</span><span class="o">=</span><span class="n">strlen</span><span class="p">(</span><span class="n">p</span><span class="p">);</span>
    <span class="kt">int</span> <span class="n">i</span><span class="o">=</span><span class="mi">0</span><span class="p">;</span><span class="kt">int</span> <span class="n">j</span><span class="o">=</span><span class="mi">0</span><span class="p">;</span>
    <span class="k">while</span><span class="p">(</span><span class="n">i</span><span class="o">&lt;</span><span class="n">slen</span><span class="o">&amp;&amp;</span><span class="n">j</span><span class="o">&lt;</span><span class="n">plen</span><span class="o">&gt;</span><span class="p">){</span>
        <span class="k">if</span><span class="p">(</span><span class="n">s</span><span class="p">[</span><span class="n">i</span><span class="p">]</span><span class="o">==</span><span class="n">p</span><span class="p">[</span><span class="n">j</span><span class="p">]){</span>
            <span class="n">i</span><span class="o">++</span><span class="p">;</span><span class="n">j</span><span class="o">++</span><span class="p">;</span>
        <span class="p">}</span>
        <span class="k">else</span> <span class="p">{</span>
            <span class="n">i</span><span class="o">=</span><span class="n">i</span><span class="o">-</span><span class="n">j</span><span class="o">+</span><span class="mi">1</span><span class="p">;</span>
            <span class="n">j</span><span class="o">=</span><span class="mi">0</span><span class="p">;</span>
        <span class="p">}</span>
    <span class="p">}</span>
    <span class="k">if</span><span class="p">(</span><span class="n">j</span><span class="o">==</span><span class="n">plen</span><span class="p">)</span> <span class="k">return</span> <span class="n">i</span><span class="o">-</span><span class="n">j</span><span class="p">;</span>
    <span class="k">else</span> <span class="k">return</span> <span class="o">-</span><span class="mi">1</span><span class="p">;</span>
<span class="p">}</span>
</pre></div>
<p>可以发现这个代码的时间复杂度很高，并且对于大规模的字符串而言，显然是会超时的.</p>
<p>但是我们可以拿一组简单的样例来模拟一下</p>
<ul>
<li>文本:BBC ABCDAB ABCDABCDABDE
<li>模板:ABCDABD
<li>第一位、第二位、第三位都不匹配，所以i每次都相当于+1.
<li>到了第四位、第五位、第六位、第七位、第八位、第九位都匹配上了，但是到模板的最后一位就没匹配上，所以我们继续调整i的位置
<li>当我们失配之后，我们已经得知S[5]=P[1]=B,而p[0]=A.那么就是说明p[1]!=p[0]，所以S[5]!=P[0]，所以继续找肯定是会失配的.
<li>既然i已经到了第9位，那么有没有方法可以让i不再回去？
</ul><p>从这里就可推出我们的新的算法：KMP.</p>
<h2 id="toc-3">KMP算法</h2>
<p>算法思路：</p>
<p>假设文本串已经匹配到了 i 位置，模板串已经到了 j 这个位置</p>
<p><li>如果 j == -1，或者当前字符串匹配成功，那么指针都可以往后移动.</p>
<p><li>如果 j != -1，且失配，那么i不变， j = next[ j ] .  失配字符对应的next值，，那么实际移动的位置位 j - next[ j ] ，且这个值大于等于1.</p>
<p>next数组的含义：代表当前字符之前的字符串中，有多大长度的相同前后缀，例如：当 next[ j ] = k，代表 j 之前的字符中最大有最大长度为 k 的相同前后缀.</p>
<p>那就是说，如果一旦失配，那么 next 数组会告诉你下一次匹配中应该跳到哪个位置，( next[ j ] 的位置 ) . 如果 next[j] 等于0或者-1 , 那么就跳到模板串的开头字符，当 next[ j ] == k , 并且 k &gt; 0 ，代表下次匹配跳到 j 之前的字符，并非开头， 并且跳过了 k 个字符 .</p>
<h4 id="toc-4">talk is cheap , show me the code!</h4>
<div class="highlight"><pre><span></span><span class="kt">int</span> <span class="nf">kmp</span><span class="p">(</span><span class="kt">char</span><span class="o">*</span> <span class="n">s</span><span class="p">,</span><span class="kt">char</span><span class="o">*</span> <span class="n">p</span><span class="p">){</span>
    <span class="kt">int</span> <span class="n">i</span><span class="o">=</span><span class="mi">0</span><span class="p">;</span><span class="kt">int</span> <span class="n">j</span><span class="o">=</span><span class="mi">0</span><span class="p">;</span>
    <span class="kt">int</span> <span class="n">slen</span><span class="o">=</span><span class="n">strlen</span><span class="p">(</span><span class="n">s</span><span class="p">);</span>
    <span class="kt">int</span> <span class="n">plen</span><span class="o">=</span><span class="n">strlen</span><span class="p">(</span><span class="n">p</span><span class="p">);</span>
    <span class="k">while</span><span class="p">(</span><span class="n">i</span><span class="o">&lt;</span><span class="n">slen</span> <span class="o">&amp;&amp;</span> <span class="n">j</span><span class="o">&lt;</span><span class="n">plen</span><span class="p">)</span>
        <span class="k">if</span><span class="p">(</span><span class="n">j</span><span class="o">==-</span><span class="mi">1</span><span class="o">||</span><span class="n">s</span><span class="p">[</span><span class="n">i</span><span class="p">]</span><span class="o">==</span><span class="n">p</span><span class="p">[</span><span class="n">j</span><span class="p">]){</span><span class="n">i</span><span class="o">++</span><span class="p">;</span><span class="n">j</span><span class="o">++</span><span class="p">;}</span>
        <span class="k">else</span> <span class="n">j</span><span class="o">=</span><span class="n">next</span><span class="p">[</span><span class="n">j</span><span class="p">];</span>
    <span class="c1">//如果j！=-1，且失配，那么i不变，j=next[j]</span>
    <span class="k">if</span><span class="p">(</span><span class="n">j</span><span class="o">==</span><span class="n">plen</span><span class="p">)</span> <span class="k">return</span> <span class="n">i</span><span class="o">-</span><span class="n">j</span><span class="p">;</span>
    <span class="k">else</span> <span class="k">return</span> <span class="o">-</span><span class="mi">1</span><span class="p">;</span>
<span class="p">}</span>
</pre></div>
<h3 id="toc-5">next数组</h3>
<p>我们拿之前的例子来说，当S[10]!=P[6]时， j 直接从6跳到2 所以相当于模板享有位移的位数就是 j - next[ j ].</p>
<p>为什么？</p>
<p>因为后面文本串又有一个AB，在模式串中也有AB，所以我们直接跳到有AB的地方就可以了.</p>
<p>现在怎么求就是一个很严重的问题了.</p>
<h4 id="toc-6">talk is cheap , show me the code!</h4>
<div class="highlight"><pre><span></span><span class="kt">void</span> <span class="nf">mknext</span><span class="p">(){</span>
    <span class="k">for</span><span class="err">（</span><span class="kt">int</span> <span class="n">q</span><span class="o">=</span><span class="mi">1</span><span class="p">,</span><span class="n">k</span><span class="o">=</span><span class="mi">0</span><span class="p">;</span><span class="n">q</span><span class="o">&lt;</span><span class="n">lenp</span><span class="p">;</span><span class="o">++</span><span class="n">q</span><span class="p">){</span>
        <span class="k">while</span><span class="p">(</span><span class="n">k</span><span class="o">&amp;&amp;</span><span class="n">p</span><span class="p">[</span><span class="n">q</span><span class="p">]</span><span class="o">!=</span><span class="n">p</span><span class="p">[</span><span class="n">k</span><span class="p">])</span> <span class="n">k</span><span class="o">=</span><span class="n">Next</span><span class="p">[</span><span class="n">k</span><span class="o">-</span><span class="mi">1</span><span class="p">];</span>
        <span class="k">if</span><span class="p">(</span><span class="n">p</span><span class="p">[</span><span class="n">q</span><span class="p">]</span><span class="o">==</span><span class="n">p</span><span class="p">[</span><span class="n">k</span><span class="p">])</span> <span class="n">k</span><span class="o">++</span><span class="p">;</span>
        <span class="n">Next</span><span class="p">[</span><span class="n">q</span><span class="p">]</span><span class="o">=</span><span class="n">k</span><span class="p">;</span>
    <span class="p">}</span>
<span class="p">}</span>
</pre></div>
<p>再举一组例子吧</p>
<p>cqsxqmmcqsxqmm</p>
<p>这个模板的next数组的值为</p>
<h2 id="toc-7">c q s x q m m c q s x q m m </h2>
<h2 id="toc-8">0  0  0  0  0  0  0  1  2  3  4  5  6  7</h2>
<p>也许对不上...（<em>hua|ji</em></p>
<p>kmp还有优化？</p>
<p>不会下一个.</p>
<p>By:Wahacer</p>
<p>2017年10月12号</p>
<p>21:10</p>


        </div>
  </div>
</div>
<!-- Footer
    ================================================== -->
<footer class="footer">
  <div class="container">
         Copyright (c) 2017 Powered By <a href="https://gitee.com/uncle-lu/oub">OUB</a>
         <a rel="license" href="http://creativecommons.org/licenses/by-nc-sa/3.0/cn/"><img alt="知识共享许可协议" style="border-width:0" src="https://i.creativecommons.org/l/by-nc-sa/3.0/cn/88x31.png" /></a><br />本作品采用<a rel="license" href="http://creativecommons.org/licenses/by-nc-sa/3.0/cn/">知识共享署名-非商业性使用-相同方式共享 3.0 中国大陆许可协议</a>进行许可。
  </div>
</footer>
<script>
    $('h1').each(function() {
        $(this).wrap('<section id="' + this.id + '"/>');
    });

    $('h1').wrap('<div class="page-header" />');
    $('h1').wrap('<div class="well well-small" />');

    $(document).ready(function() {
        var items = [];
        $('h1').each(function() {
            items.push('<li><a href="#' + this.id + '"><i class="fa fa-chevron-right pull-right"></i> ' + $(this).text() + '</a></li>');
        });  // close each()

    $('#sidebar_list').append( items.join('') );

    $('table').each(function() {
        $(this).addClass('table table-striped table-condensed table-hover');
    });

    $('.done0').each(function() {
        $(this).html('<div class="alert alert-info"><i class="fa fa-check-square-o"></i>'+$(this).html()+'</div></li>');
    });

    $('.done4').each(function() {
        $(this).html('<div class="alert alert-success"><i class="fa fa-square-o"></i>'+$(this).html()+'</div></li>');
    });
   
    $('pre').each(function() {
        $(this).html('<code>'+$(this).html()+'</code>');
    });
    hljs.initHighlightingOnLoad();
});
</script>
</body>
</html>